package com.lzq.leetcode.hoot100;

public class s32 {

    public int longestValidParentheses(String s) {

        int len = s.length();
        int[] dp = new int[len];
        int max = 0;
        for (int i=1; i<len; i++) {

            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = 2 + (i >= 2 ? dp[i-2] : 0);
                } else {
                    int pre = i - dp[i-1] - 1;
                    if (pre >= 0 && s.charAt(pre) == '(') {
                        dp[i] = (pre >= 1 ? dp[pre - 1] : 0) + (i - pre + 1);
                    }
                }
            }

            max = Math.max(max, dp[i]);
        }

        return max;
    }

    public static void main(String[] args) {
        s32 s32 = new s32();
        System.out.println(s32.longestValidParentheses("()(())"));
    }
}
